#include "Extern.h"
#include <string>
#include <cstdlib>

BTNode::BTNode(int size, bool leaf, BufferManager * manager, int level) : Page(size, manager)
{
	isLeaf = leaf;
	maxKeyNum = (int)(size / (INTSIZE + NODESIZE));
	keyNum = 0;
	nodeLevel = level;

	leftFence = MININT;
	rightFence = MAXINT;

	pageId = bm->RequestID();
	bm->AddEntry(this, pageId);
	pre = next = NULL;

	keys = new KEY[maxKeyNum + 1];
	pointers = new BTNode *[maxKeyNum + 2];
	for(int i = 0; i < maxKeyNum + 2; i++)
		pointers[i] = NULL;
}

// insert key into leaf node
BTNode * BTNode::InsertKeyIntoLeaf(KEY key)
{
	LoadFromFile();
	bm->WriteUpdate(pageId);

	BTNode * retNode = NULL;
	if(!isLeaf)
	{
		cout << "Error! the key should be inserted into a leaf node!" << endl;
		return NULL;
	}

	InsertKeyIntoNONFullLeaf(key);

	bm->his->InsertKey(key);
	
	if (IsFull()) // leaf split is needed
		retNode = SplitLeaf();

	return retNode;
}

BTNode * BTNode::SplitLeaf()
{
	LoadFromFile();
	bm->WriteUpdate(pageId);
	BTNode * retNode = NULL;
	int splitPoint = GetSplitPoint();
	if(splitPoint == -1) // the keys in this node are all same
	{
		keyNum--;
		return NULL;
	}

	BTNode * newNode = new BTNode(pageSize, true, bm, nodeLevel);
	for(int i = splitPoint; i < keyNum; i++)
		newNode->keys[i - splitPoint] = keys[i];
	keyNum = splitPoint;
	newNode->keyNum = maxKeyNum + 1 - keyNum;

	newNode->LoadFromFile();
	newNode->bm->ReadUpdate(newNode->pageId);
	newNode->bm->WriteUpdate(newNode->pageId);

	newNode->pre = this;
	newNode->next = next;
	if(next)
		next->pre = newNode;
	next = newNode;

	newNode->rightFence = rightFence;
	rightFence = newNode->keys[0];
	newNode->leftFence = newNode->keys[0];

	if(!node_trace[nodeLevel + 1])
	{
		BTNode * newroot = new BTNode(pageSize, false, bm, nodeLevel + 1);
		newroot->keyNum = 1;
		newroot->keys[0] = newNode->keys[0];
		newroot->pointers[0] = this;
		newroot->pointers[1] = newNode;
		retNode = newroot;
		newroot->LoadFromFile();
		newroot->bm->ReadUpdate(newroot->pageId);
		newroot->bm->WriteUpdate(newroot->pageId);
	}
	else
	{
		node_trace[nodeLevel + 1]->InsertKeyIntoNONFullNONLeaf(newNode->keys[0], this, newNode);

		if(node_trace[nodeLevel + 1]->IsFull())
			retNode = node_trace[nodeLevel + 1]->SplitNONLeaf();
	}

	return retNode;
}

BTNode * BTNode::SplitNONLeaf()
{
	BTNode * retNode = NULL;
	int splitPoint = GetSplitPoint();

	BTNode * newNode = new BTNode(pageSize, false, bm, nodeLevel);
	for(int i = splitPoint + 1; i < keyNum; i++)
	{
		newNode->keys[i - splitPoint - 1] = keys[i];
		newNode->pointers[i - splitPoint - 1] = pointers[i];
	}
	newNode->pointers[maxKeyNum - splitPoint] = pointers[maxKeyNum + 1];

	newNode->LoadFromFile();
	newNode->bm->ReadUpdate(newNode->pageId);
	newNode->bm->WriteUpdate(newNode->pageId);

	keyNum = splitPoint;
	newNode->keyNum = maxKeyNum - keyNum;

	newNode->rightFence = rightFence;
	rightFence = keys[splitPoint];
	newNode->leftFence = keys[splitPoint];

	if(!node_trace[nodeLevel + 1])
	{
		BTNode * newroot = new BTNode(pageSize, false, bm, nodeLevel + 1);
		newroot->keyNum = 1;
		newroot->keys[0] = keys[splitPoint];
		newroot->pointers[0] = this;
		newroot->pointers[1] = newNode;
		retNode = newroot;
		newroot->LoadFromFile();
		newroot->bm->ReadUpdate(newroot->pageId);
		newroot->bm->WriteUpdate(newroot->pageId);
	}
	else
	{
		node_trace[nodeLevel + 1]->InsertKeyIntoNONFullNONLeaf(keys[splitPoint], this, newNode);

		if(node_trace[nodeLevel + 1]->IsFull())
			retNode = node_trace[nodeLevel + 1]->SplitNONLeaf();
	}
	return retNode;
}

int BTNode::GetSplitPoint()
{
	int middle = (maxKeyNum + 1) >> 1;
	for(int i = 1; i < middle + 1; i++)
	{
		if(keys[middle - i] != keys[middle])
			return middle - i + 1;
		if(middle + i < keyNum && keys[middle + i] != keys[middle])
			return middle + i;
	}
	return -1;
}

void BTNode::InsertKeyIntoNONFullLeaf(KEY key)
{
	int i = 0, index = keyNum;
	for(; i < keyNum; i++)
	{
		if(keys[i] > key)
		{
			index = i;
			break;
		}
	}
	for(i = keyNum - 1; i >= index; i--)
	{
		keys[i + 1] = keys[i];
		pointers[i + 1] = pointers[i];
	}
	keys[index] = key;
	pointers[index] = NULL;
	keyNum++;
}

void BTNode::InsertKeyIntoNONFullNONLeaf(KEY key, BTNode * left, BTNode * right)
{
	LoadFromFile();
	bm->WriteUpdate(pageId);

	int index = FindInNONLeaf(key);
	for(int i = keyNum; i > index; i--)
	{
		keys[i] = keys[i - 1];
		pointers[i + 1] = pointers[i];
	}

	keys[index] = key;
	pointers[index] = left;
	pointers[index + 1] = right;

	left->rightFence = key;
	right->leftFence = key;
	keyNum++;
}

int BTNode::FindInNONLeaf(KEY key)
{
	int i = 0, result = -1;
	for (; i < keyNum; i++) 
	{
		if(keys[i] > key)
		{
			result = i;
			break;
		}
		else if(keys[i] == key)
		{
			result = i + 1;
			break;
		}
	}
	if(result == -1) 
		result = keyNum;
	return result;
}

int BTNode::FindInLeaf(KEY key)
{
	int i = 0, result = -1;
	for (; i < keyNum; i++) 
	{
		if(keys[i] == key)
		{
			result = key;
			break;
		}
	}
	return result;
}

BTNode * BTNode::FindNode(KEY key)
{
	LoadFromFile();
	bm->ReadUpdate(pageId);

	if(isLeaf)
	{
		node_trace[nodeLevel] = this;
		return this;
	}
	else
	{
		int index = FindInNONLeaf(key);
		node_trace[nodeLevel] = this;
		return pointers[index]->FindNode(key);
	}
}

KEY BTNode::PointQuery(KEY querykey)
{
	BTNode * leaf = FindNode(querykey);
	return leaf->FindInLeaf(querykey);
}
